{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2025 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# slitherlink"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/contrib/slitherlink.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/examples/contrib/slitherlink.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.constraint_solver import pywrapcp\n",
    "from collections import deque\n",
    "\n",
    "small = [[3, 2, -1, 3], [-1, -1, -1, 2], [3, -1, -1, -1], [3, -1, 3, 1]]\n",
    "\n",
    "medium = [[-1, 0, -1, 1, -1, -1, 1, -1], [-1, 3, -1, -1, 2, 3, -1, 2],\n",
    "          [-1, -1, 0, -1, -1, -1, -1, 0], [-1, 3, -1, -1, 0, -1, -1, -1],\n",
    "          [-1, -1, -1, 3, -1, -1, 0, -1], [1, -1, -1, -1, -1, 3, -1, -1],\n",
    "          [3, -1, 1, 3, -1, -1, 3, -1], [-1, 0, -1, -1, 3, -1, 3, -1]]\n",
    "\n",
    "big = [[3, -1, -1, -1, 2, -1, 1, -1, 1, 2], [1, -1, 0, -1, 3, -1, 2, 0, -1, -1],\n",
    "       [-1, 3, -1, -1, -1, -1, -1, -1, 3, -1],\n",
    "       [2, 0, -1, 3, -1, 2, 3, -1, -1, -1], [-1, -1, -1, 1, 1, 1, -1, -1, 3, 3],\n",
    "       [2, 3, -1, -1, 2, 2, 3, -1, -1, -1], [-1, -1, -1, 1, 2, -1, 2, -1, 3, 3],\n",
    "       [-1, 2, -1, -1, -1, -1, -1, -1, 2, -1],\n",
    "       [-1, -1, 1, 1, -1, 2, -1, 1, -1, 3], [3, 3, -1, 1, -1, 2, -1, -1, -1, 2]]\n",
    "\n",
    "\n",
    "def NeighboringArcs(i, j, h_arcs, v_arcs):\n",
    "  tmp = []\n",
    "  if j > 0:\n",
    "    tmp.append(h_arcs[i][j - 1])\n",
    "  if j < len(v_arcs) - 1:\n",
    "    tmp.append(h_arcs[i][j])\n",
    "  if i > 0:\n",
    "    tmp.append(v_arcs[j][i - 1])\n",
    "  if i < len(h_arcs) - 1:\n",
    "    tmp.append(v_arcs[j][i])\n",
    "  return tmp\n",
    "\n",
    "\n",
    "def PrintSolution(data, h_arcs, v_arcs):\n",
    "  num_rows = len(data)\n",
    "  num_columns = len(data[0])\n",
    "\n",
    "  for i in range(num_rows):\n",
    "    first_line = ''\n",
    "    second_line = ''\n",
    "    third_line = ''\n",
    "    for j in range(num_columns):\n",
    "      h_arc = h_arcs[i][j].Value()\n",
    "      v_arc = v_arcs[j][i].Value()\n",
    "      cnt = data[i][j]\n",
    "      first_line += ' ---' if h_arc else '    '\n",
    "      second_line += '|' if v_arc else ' '\n",
    "      second_line += '   ' if cnt == -1 else ' %i ' % cnt\n",
    "      third_line += '|   ' if v_arc == 1 else '    '\n",
    "    termination = v_arcs[num_columns][i].Value()\n",
    "    second_line += '|' if termination else ' '\n",
    "    third_line += '|' if termination else ' '\n",
    "    print(first_line)\n",
    "    print(third_line)\n",
    "    print(second_line)\n",
    "    print(third_line)\n",
    "  last_line = ''\n",
    "  for j in range(num_columns):\n",
    "    h_arc = h_arcs[num_rows][j].Value()\n",
    "    last_line += ' ---' if h_arc else '    '\n",
    "  print(last_line)\n",
    "\n",
    "\n",
    "class BooleanSumEven(pywrapcp.PyConstraint):\n",
    "\n",
    "  def __init__(self, solver, vars):\n",
    "    pywrapcp.PyConstraint.__init__(self, solver)\n",
    "    self.__vars = vars\n",
    "    self.__num_possible_true_vars = pywrapcp.NumericalRevInteger(0)\n",
    "    self.__num_always_true_vars = pywrapcp.NumericalRevInteger(0)\n",
    "\n",
    "  def Post(self):\n",
    "    for i in range(len(self.__vars)):\n",
    "      v = self.__vars[i]\n",
    "      if not v.Bound():\n",
    "        demon = self.Demon(BooleanSumEven.Update, i)\n",
    "        v.WhenBound(demon)\n",
    "\n",
    "  def InitialPropagate(self):\n",
    "    num_always_true = 0\n",
    "    num_possible_true = 0\n",
    "    possible_true_index = -1\n",
    "    for i in range(len(self.__vars)):\n",
    "      var = self.__vars[i]\n",
    "      if var.Min() == 1:\n",
    "        num_always_true += 1\n",
    "        num_possible_true += 1\n",
    "      elif var.Max() == 1:\n",
    "        num_possible_true += 1\n",
    "        possible_true_index = i\n",
    "\n",
    "    if num_always_true == num_possible_true and num_possible_true % 2 == 1:\n",
    "      self.solver().Fail()\n",
    "\n",
    "    if num_possible_true == num_always_true + 1:\n",
    "      self.__vars[possible_true_index].SetValue(num_always_true % 2)\n",
    "\n",
    "    self.__num_possible_true_vars.SetValue(self.solver(), num_possible_true)\n",
    "    self.__num_always_true_vars.SetValue(self.solver(), num_always_true)\n",
    "\n",
    "  def Update(self, index):\n",
    "    solver = self.solver()\n",
    "    value = self.__vars[index].Value()\n",
    "    if value == 0:\n",
    "      self.__num_possible_true_vars.Decr(solver)\n",
    "    else:\n",
    "      self.__num_always_true_vars.Incr(solver)\n",
    "\n",
    "    num_possible = self.__num_possible_true_vars.Value()\n",
    "    num_always = self.__num_always_true_vars.Value()\n",
    "\n",
    "    if num_always == num_possible and num_possible % 2 == 1:\n",
    "      solver.Fail()\n",
    "\n",
    "    if num_possible == num_always + 1:\n",
    "      possible_true_index = -1\n",
    "      for i in range(len(self.__vars)):\n",
    "        if not self.__vars[i].Bound():\n",
    "          possible_true_index = i\n",
    "          break\n",
    "\n",
    "      if possible_true_index != -1:\n",
    "        self.__vars[possible_true_index].SetValue(num_always % 2)\n",
    "\n",
    "  def DebugString(self):\n",
    "    return 'BooleanSumEven'\n",
    "\n",
    "\n",
    "# Dedicated constraint: There is a single path on the grid.\n",
    "# This constraint does not enforce the non-crossing, this is done\n",
    "# by the constraint on the degree of each node.\n",
    "class GridSinglePath(pywrapcp.PyConstraint):\n",
    "\n",
    "  def __init__(self, solver, h_arcs, v_arcs):\n",
    "    pywrapcp.PyConstraint.__init__(self, solver)\n",
    "    self.__h_arcs = h_arcs\n",
    "    self.__v_arcs = v_arcs\n",
    "\n",
    "  def Post(self):\n",
    "    demon = self.DelayedInitialPropagateDemon()\n",
    "    for row in self.__h_arcs:\n",
    "      for var in row:\n",
    "        var.WhenBound(demon)\n",
    "\n",
    "    for column in self.__v_arcs:\n",
    "      for var in column:\n",
    "        var.WhenBound(demon)\n",
    "\n",
    "  # This constraint implements a single propagation.\n",
    "  # If one point is on the path, it checks the reachability of all possible\n",
    "  # nodes, and zero out the unreachable parts.\n",
    "  def InitialPropagate(self):\n",
    "    num_rows = len(self.__h_arcs)\n",
    "    num_columns = len(self.__v_arcs)\n",
    "\n",
    "    num_points = num_rows * num_columns\n",
    "    root_node = -1\n",
    "    possible_points = set()\n",
    "    neighbors = [[] for _ in range(num_points)]\n",
    "\n",
    "    for i in range(num_rows):\n",
    "      for j in range(num_columns - 1):\n",
    "        h_arc = self.__h_arcs[i][j]\n",
    "        if h_arc.Max() == 1:\n",
    "          head = i * num_columns + j\n",
    "          tail = i * num_columns + j + 1\n",
    "          neighbors[head].append(tail)\n",
    "          neighbors[tail].append(head)\n",
    "          possible_points.add(head)\n",
    "          possible_points.add(tail)\n",
    "          if root_node == -1 and h_arc.Min() == 1:\n",
    "            root_node = head\n",
    "\n",
    "    for i in range(num_rows - 1):\n",
    "      for j in range(num_columns):\n",
    "        v_arc = self.__v_arcs[j][i]\n",
    "        if v_arc.Max() == 1:\n",
    "          head = i * num_columns + j\n",
    "          tail = (i + 1) * num_columns + j\n",
    "          neighbors[head].append(tail)\n",
    "          neighbors[tail].append(head)\n",
    "          possible_points.add(head)\n",
    "          possible_points.add(tail)\n",
    "          if root_node == -1 and v_arc.Min() == 1:\n",
    "            root_node = head\n",
    "\n",
    "    if root_node == -1:\n",
    "      return\n",
    "\n",
    "    visited_points = set()\n",
    "    to_process = deque()\n",
    "\n",
    "    # Compute reachable points\n",
    "    to_process.append(root_node)\n",
    "    while to_process:\n",
    "      candidate = to_process.popleft()\n",
    "      visited_points.add(candidate)\n",
    "      for neighbor in neighbors[candidate]:\n",
    "        if not neighbor in visited_points:\n",
    "          to_process.append(neighbor)\n",
    "          visited_points.add(neighbor)\n",
    "\n",
    "    if len(visited_points) < len(possible_points):\n",
    "      for point in visited_points:\n",
    "        possible_points.remove(point)\n",
    "\n",
    "      # Loop on unreachable points and zero all neighboring arcs.\n",
    "      for point in possible_points:\n",
    "        i = point // num_columns\n",
    "        j = point % num_columns\n",
    "        neighbors = NeighboringArcs(i, j, self.__h_arcs, self.__v_arcs)\n",
    "        for var in neighbors:\n",
    "          var.SetMax(0)\n",
    "\n",
    "\n",
    "def SlitherLink(data):\n",
    "  num_rows = len(data)\n",
    "  num_columns = len(data[0])\n",
    "\n",
    "  solver = pywrapcp.Solver('slitherlink')\n",
    "  h_arcs = [[\n",
    "      solver.BoolVar('h_arcs[%i][%i]' % (i, j)) for j in range(num_columns)\n",
    "  ] for i in range(num_rows + 1)]\n",
    "\n",
    "  v_arcs = [[\n",
    "      solver.BoolVar('v_arcs[%i][%i]' % (i, j)) for j in range(num_rows)\n",
    "  ] for i in range(num_columns + 1)]\n",
    "\n",
    "  # Constraint on the sum or arcs\n",
    "  for i in range(num_rows):\n",
    "    for j in range(num_columns):\n",
    "      if data[i][j] != -1:\n",
    "        sq = [h_arcs[i][j], h_arcs[i + 1][j], v_arcs[j][i], v_arcs[j + 1][i]]\n",
    "        solver.Add(solver.SumEquality(sq, data[i][j]))\n",
    "\n",
    "  # Single loop: each node has a degree 0 or 2\n",
    "  zero_or_two = [0, 2]\n",
    "  for i in range(num_rows + 1):\n",
    "    for j in range(num_columns + 1):\n",
    "      neighbors = NeighboringArcs(i, j, h_arcs, v_arcs)\n",
    "      solver.Add(solver.Sum(neighbors).Member(zero_or_two))\n",
    "\n",
    "  # Single loop: sum or arcs on row or column is even\n",
    "  for i in range(num_columns):\n",
    "    column = [h_arcs[j][i] for j in range(num_rows + 1)]\n",
    "    solver.Add(BooleanSumEven(solver, column))\n",
    "\n",
    "  for i in range(num_rows):\n",
    "    row = [v_arcs[j][i] for j in range(num_columns + 1)]\n",
    "    solver.Add(BooleanSumEven(solver, row))\n",
    "\n",
    "  # Single loop: main constraint\n",
    "  solver.Add(GridSinglePath(solver, h_arcs, v_arcs))\n",
    "\n",
    "  # Special rule on corners: value == 3 implies 2 border arcs used.\n",
    "  if data[0][0] == 3:\n",
    "    h_arcs[0][0].SetMin(1)\n",
    "    v_arcs[0][0].SetMin(1)\n",
    "  if data[0][num_columns - 1] == 3:\n",
    "    h_arcs[0][num_columns - 1].SetMin(1)\n",
    "    v_arcs[num_columns][0].SetMin(1)\n",
    "  if data[num_rows - 1][0] == 3:\n",
    "    h_arcs[num_rows][0].SetMin(1)\n",
    "    v_arcs[0][num_rows - 1].SetMin(1)\n",
    "  if data[num_rows - 1][num_columns - 1] == 3:\n",
    "    h_arcs[num_rows][num_columns - 1].SetMin(1)\n",
    "    v_arcs[num_columns][num_rows - 1].SetMin(1)\n",
    "\n",
    "  # Search\n",
    "  all_vars = []\n",
    "  for row in h_arcs:\n",
    "    all_vars.extend(row)\n",
    "  for column in v_arcs:\n",
    "    all_vars.extend(column)\n",
    "\n",
    "  db = solver.Phase(all_vars, solver.CHOOSE_FIRST_UNBOUND,\n",
    "                    solver.ASSIGN_MAX_VALUE)\n",
    "\n",
    "  log = solver.SearchLog(1000000)\n",
    "\n",
    "  solver.NewSearch(db, log)\n",
    "  while solver.NextSolution():\n",
    "    PrintSolution(data, h_arcs, v_arcs)\n",
    "  solver.EndSearch()\n",
    "\n",
    "\n",
    "SlitherLink(small)\n",
    "SlitherLink(medium)\n",
    "SlitherLink(big)\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
